
export class QuadTree {

    nodes: Array<QuadTree> = [];
    objects: Array<cc.Node> = [];
    maxObjects: number = 0;
    maxLevels: number = 0;
    rect: cc.Rect = new cc.Rect();
    level: number = 0;

    ctx: cc.Graphics = null
    // 以左下角为原点坐标
    //{x, y, width, height}
    /**
     * 
     * @param rect  一个Rect对象 {x, y, width, height}
     * @param maxObject 最大节点数
     * @param maxLevel 最大深度
     * @param level 初始深度
     */
    constructor(rect: cc.Rect, maxObjects, maxLevels, level = 0) {
        // 每个树节点的最大叶子节点个数
        this.maxObjects = maxObjects || 10;
        // 最大深度
        this.maxLevels = maxLevels || 4;
        // 当前深度
        this.level = level;
        // 当前包围盒
        this.rect = rect;
        // 树节点数组
        this.nodes = [];
        // 叶子节点数组
        this.objects = [];
    }
    // 切割四块区域
    private split() {
        let nextLevel = this.level + 1,
            x = this.rect.x,
            y = this.rect.y,
            subWidth = this.rect.width / 2,
            subHeight = this.rect.height / 2;

        // 分成四个象限的树节点
        // 第一象限
        this.nodes[0] = new QuadTree(new cc.Rect(
            x + subWidth,
            y + subHeight,
            subWidth,
            subHeight,
        ), this.maxObjects, this.maxLevels, nextLevel);
        // 第二象限
        this.nodes[1] = new QuadTree(new cc.Rect(
            x,
            y + subHeight,
            subWidth,
            subHeight,
        ), this.maxObjects, this.maxLevels, nextLevel);
        // 第三象限
        this.nodes[2] = new QuadTree(new cc.Rect(
            x,
            y,
            subWidth,
            subHeight,
        ), this.maxObjects, this.maxLevels, nextLevel);
        // 第四象限
        this.nodes[3] = new QuadTree(new cc.Rect(
            x + subWidth,
            y,
            subWidth,
            subHeight,
        ), this.maxObjects, this.maxLevels, nextLevel);

    }
    // 获取所在象限的数组（因为可能跨多个象限，所以需要数组）
    private getQuadrantIds(rect: cc.Rect) {
        let midx = this.rect.x + this.rect.width / 2,
            midy = this.rect.y + this.rect.height / 2,
            startInNorth = rect.y + rect.height > midy,
            startInWest = rect.x <= midx,
            endInSouth = rect.y <= midy,
            endInEast = rect.x + rect.width > midx;
        let ids = [];
        // 第一象限
        if (startInNorth && endInEast) {
            ids.push(0)
        }
        // 第二象限
        if (startInNorth && startInWest) {
            ids.push(1)
        }
        // 第三象限
        if (endInSouth && startInWest) {
            ids.push(2)
        }
        // 第四象限
        if (endInSouth && endInEast) {
            ids.push(3)
        }
        return ids;
    }
    /**删除节点 */
    delete(object: cc.Node) {
        if (this.objects.length) {
            if (this.objects.includes(object)) {
                this.objects.splice(this.objects.indexOf(object), 1);
            }
        }
        if (this.nodes.length) {
            for (let i = 0; i < this.nodes.length; i++) {
                this.nodes[i].delete(object);
            }
        }
    }

    // 插入节点
    insert(object: cc.Node) {
        // 如果有子节点，并且有匹配的象限就调用子节点的insert
        let ids, i = 0;
        if (this.nodes.length) {
            ids = this.getQuadrantIds(object.getBoundingBoxToWorld());
            for (i = 0; i < ids.length; i++) {
                this.nodes[ids[i]].insert(object);
            }
            return;
        }
        if (!this.objects.includes(object)) {
            this.objects.push(object);
        }

        // 如果该节点的子节点超过最大值，并且没超过最大深度，就全部取出来，塞到子象限去
        if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
            if (!this.nodes.length) {
                this.split();
            }
            let o: cc.Node;
            for (i = 0; i < this.objects.length; i++) {
                o = this.objects[i];
                ids = this.getQuadrantIds(o.getBoundingBoxToWorld());
                for (let j = 0; j < ids.length; j++) {
                    this.nodes[ids[j]].insert(o);
                }
            }
            this.objects = [];
        }
    }

    // 取出需要符合条件的包围盒节点
    retrieve(rect): Array<cc.Node> {
        let objects = this.objects,
            ids = this.getQuadrantIds(rect)
            ;
        if (this.nodes.length) {
            for (let i = 0; i < ids.length; i++) {
                objects = objects.concat(this.nodes[ids[i]].retrieve(rect));
            }
        }
        objects = objects.filter((v, i) => {
            return objects.indexOf(v) >= i;
        })

        return objects;
    }
    // 清理所有树节点
    clear() {
        this.objects = [];
        for (var i = 0; i < this.nodes.length; i++) {
            if (this.nodes.length) {
                this.nodes[i].clear();
            }
        }
        this.nodes = [];
    }
    // 获取所有树节点
    getAllNodes(): QuadTree[] {
        let nodes = this.nodes;
        if (nodes.length) {
            for (let i = 0; i < nodes.length; i++) {
                nodes = nodes.concat(nodes[i].getAllNodes());
            }
        }
        return nodes;
    }
    // 获取所有树节点
    getAllObject(): cc.Node[] {
        let nodes = this.nodes;
        let objects = this.objects;
        if (nodes.length) {
            for (let i = 0; i < nodes.length; i++) {
                objects = objects.concat(nodes[i].getAllObject());
            }
        }
        return objects;
    }

    // 更新树（如果需要动态更新树），就在每一帧调用一次，这会判断是否改节点仍然再原有象限
    refresh(root: QuadTree) {
        let i = 0;
        // 如果存在包围盒对象则不需要往下遍历
        if (this.objects.length) {
            let isInner = (rect: cc.Rect, bounds: cc.Rect) => {
                return (
                    rect.x >= bounds.x
                    && rect.x + rect.width <= bounds.x + bounds.width
                    && rect.y >= bounds.y
                    && rect.y + rect.height <= bounds.y + bounds.height
                )
            }
            let arr = [];
            for (i = 0; i < this.objects.length;) {
                if (!isInner(this.objects[i].getBoundingBoxToWorld(), this.rect)) {
                    arr.push(this.objects.splice(i, 1)[0]);
                    continue;
                }
                i++;
            }
            if (arr.length) {
                for (i = 0; i < arr.length; i++) {
                    root.insert(arr[i]);
                }
            }
        } else if (this.nodes.length) {
            for (i = 0; i < this.nodes.length; i++) {
                this.nodes[i].refresh(root);
            }
        }
    }
}

